import tkinter as tk
from tkinter import messagebox
from tkinter import *
import random
import math

# 该类的实现来自网络 https://www.jianshu.com/p/53d1cab0f2f5


class SudokuMaker(object):
    def __init__(self):
        self.matrix = []

    # 生成一个随机的数组
    def get_random_unit(self):
        _num_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
        random.shuffle(_num_list)
        return _num_list

    def print_grid(self, arr):
        for i in range(9):
            print(arr[i])

    def get_row(self, row):
        row_arr = []
        for v in self.matrix[row]:
            if v == 0:
                continue
            row_arr.append(v)
        return row_arr

    def get_col(self, col):
        col_arr = []
        for i in range(9):
            val = self.matrix[i][col]
            if val == 0:
                continue
            col_arr.append(self.matrix[i][col])
        return col_arr

    def get_block(self, num):
        col_arr = []
        seq = num % 3
        col_end = 9 if seq == 0 else seq * 3
        row_end = int(math.ceil(num / 3) * 3)
        for i in range(row_end - 3, row_end):
            for j in range(col_end - 3, col_end):
                val = self.matrix[i][j]
                if val != 0:
                    col_arr.append(self.matrix[i][j])
        return col_arr

    def get_block_seq(self, row, col):
        col_seq = int(math.ceil((col + 0.1) / 3))
        row_seq = int(math.ceil((row + 0.1) / 3))
        return 3 * (row_seq - 1) + col_seq

    def get_enable_arr(self, row, col):
        avail_arr = self.get_random_unit()
        seq = self.get_block_seq(row, col)
        block = self.get_block(seq)
        row = self.get_row(row)
        col = self.get_col(col)
        unable_arr = list(set(block + row + col))
        for v in unable_arr:
            if v in avail_arr:
                avail_arr.remove(v)
        return avail_arr

    def main(self):
        can_num = {}
        count = 0
        # 初始化一个9行9列的数组
        for i in range(9):
            self.matrix.append([0] * 9)

        num_list = self.get_random_unit()
        for row in range(3):
            for col in range(3):
                self.matrix[row][col] = num_list.pop(0)

        num_list = self.get_random_unit()
        for row in range(3, 6):
            for col in range(3, 6):
                self.matrix[row][col] = num_list.pop(0)

        num_list = self.get_random_unit()
        for row in range(6, 9):
            for col in range(6, 9):
                self.matrix[row][col] = num_list.pop(0)

        box_list = []
        for row in range(9):
            for col in range(9):
                if self.matrix[row][col] == 0:
                    box_list.append({'row': row, 'col': col})

        i = 0
        while i < len(box_list):
            count += 1
            position = box_list[i]
            row = position['row']
            col = position['col']
            key = '%dx%d' % (row, col)
            if key in can_num:
                enable_arr = can_num[key]
            else:
                enable_arr = self.get_enable_arr(row, col)
                can_num[key] = enable_arr

            if len(enable_arr) <= 0:
                i -= 1
                if key in can_num:
                    del (can_num[key])
                self.matrix[row][col] = 0
                continue
            else:
                self.matrix[row][col] = enable_arr.pop()
                i += 1

        # self.print_grid(self.matrix)
        # print(count)


class Sudoku(object):
    def __init__(self):
        self.origin_sudoku = [[0]*10 for i in range(10)]
        self.sudoku = [[0]*10 for i in range(10)]
        #self.problem_sudoku = [[0]*10 for i in range(10)]
        self.covered = [[0]*10 for i in range(10)]
        self.rule = [0, 0, 0]
        self.__sm = SudokuMaker()

    def check(self):
        if self.__checkRowCol() or self.__checkGrid():
            return True
        else:
            return False

    def __checkRowCol(self):
        for i in range(1, 10):
            (flag_row, flag_col) = ([False]*10, [False]*10)
            for j in range(1, 10):
                if self.sudoku[i][j] == 0:
                    continue
                if flag_row[self.sudoku[i][j]]:
                    return True
                else:
                    flag_row[self.sudoku[i][j]] = True
                if flag_col[self.sudoku[i][j]]:
                    return True
                else:
                    flag_col[self.sudoku[i][j]] = True

        return False

    def __checkGrid(self):
        for grid in range(0, 9):
            flag = [False]*10
            row = int(grid / 3) * 3 + 1
            col = int(grid % 3 * 3) + 1
            for i in range(3):
                for j in range(3):
                    if self.sudoku[row+i][col+j] == 0:
                        continue
                    if flag[self.sudoku[row + i][col + j]]:
                        return True
                    else:
                        flag[self.sudoku[row + i][col + j]] = True

        return False

    def print(self):
        self.__sm.print_grid(self.__sm.matrix)
        for i in range(10):
            print(self.sudoku[i])

    def checkSuccess(self):
        if self.check():
            return False
        for i in range(1,10):
            for j in range(1,10):
                if(self.sudoku[i][j] == 0):
                    return False

        return True


    def makeProblem(self):
        self.__makeSudoku()
        num_of_zeros = random.randint(30, 60)

        for grid in range(9):
            row_min = int(grid / 3) * 3 + 1
            col_min = int(grid % 3) * 3 + 1

            for i in range(3):  # 每个3*3的宫格挖3个空
                row = random.randint(row_min, row_min + 2)
                col = random.randint(col_min, col_min + 2)
                while self.sudoku[row][col] != 0:
                    self.sudoku[row][col] = 0
                    row = random.randint(row_min, row_min + 2)
                    col = random.randint(col_min, col_min + 2)

        num_of_zeros -= 3 * 9

        while num_of_zeros != 0:
            num_of_zeros -= 1
            row = random.randint(1, 9)
            col = random.randint(1, 9)
            while self.sudoku[row][col] != 0:
                self.sudoku[row][col] = 0
                row = random.randint(1, 9)
                col = random.randint(1, 9)

        for i in range(1, 10):
            self.origin_sudoku[i][:] = self.sudoku[i][:]
        
        self.__initSolver()

    def solveSudoku(self):
        self.__initSolver()
        self.__solveSudoku(1, 1)

    def __makeSudoku(self):
        self.__sm.main()
        for i in range(9):
            self.sudoku[i+1][1:] = self.__sm.matrix[i][:]
        while self.check():
            self.__sm.main()
            for i in range(9):
                self.sudoku[i+1][1:] = self.__sm.matrix[i][:]

    def __findGridIndex(self, row, col):
        return int((row - 1) / 3) * 3 + int((col - 1) / 3)

    def __findNextValue(self, row, col, value):
        index = self.__findGridIndex(row, col)
        for i in range(value, 10):
            if self.rule[0][row][i]:
                continue
            if self.rule[1][col][i]:
                continue
            if self.rule[2][index][i]:
                continue
            return i
        return 0

    def __changeRule(self, row, col, state):
        index = self.__findGridIndex(row, col)
        value = self.sudoku[row][col]
        self.rule[0][row][value] = state
        self.rule[1][col][value] = state
        self.rule[2][index][value] = state

    def __initSolver(self):
        self.covered = [[0]*10 for i in range(10)]
        self.rule[0] = [[0]*10 for i in range(10)]
        self.rule[1] = [[0]*10 for i in range(10)]
        self.rule[2] = [[0]*10 for i in range(10)]
        for i in range(10):
            for j in range(10):
                if self.sudoku[i][j] != 0:
                    self.covered[i][j] = 1
                    self.__changeRule(i, j, 1)

    def __findIdx(self, row_idx, col_idx):
        if (col_idx == 10):
            row_idx += 1
            col_idx = 1

            # 找到需要填空的位置
        while (row_idx < 10 and self.covered[row_idx][col_idx] != 0):
            col_idx += 1
            if col_idx == 10:
                row_idx += 1
                col_idx = 1

        if row_idx > 9:
            return (0, 0)
        return (row_idx, col_idx)

    def __solveSudoku(self, row_idx, col_idx):
        (row_idx, col_idx) = self.__findIdx(row_idx, col_idx)
        if (row_idx, col_idx) == (0, 0):
            return True
            # findNextValue就是找到可以在此位置填充的值
        self.sudoku[row_idx][col_idx] = self.__findNextValue(
            row_idx, col_idx, self.sudoku[row_idx][col_idx] + 1)
        while (self.sudoku[row_idx][col_idx] != 0):
            self.__changeRule(row_idx, col_idx, 1)
            if self.__solveSudoku(row_idx, col_idx + 1):
                return True
            self.__changeRule(row_idx, col_idx, 0)
            self.sudoku[row_idx][col_idx] = self.__findNextValue(
                row_idx, col_idx, self.sudoku[row_idx][col_idx] + 1)
        return False


class MainWindow(object):
    def __init__(self):
        
        self.main_window = tk.Tk()

        self.main_window.title("Sudoku Game")
        self.main_window.geometry("1000x760")

        self.frame_sudoku = tk.Frame(self.main_window,width=15, height=2)
        self.frame_sudoku.place(x=0,y=0, anchor='nw')

        self.frame_menu = tk.Frame(self.main_window,width=15, height=36).place(x=1000,y=10,anchor='nw')
        i = 1
        self.btn_new_game = tk.Button(self.frame_menu, text="新游戏", width=15, height=2, background="light blue", command=self.newGame)
        self.btn_new_game.place(x=840,y=40 * i, anchor='nw')

        i += 1
        self.btn_exit = tk.Button(self.frame_menu, text="退出", width=15, height=2, background="light blue", command=self.main_window.quit)
        self.btn_exit.place(x=840,y=40 * i, anchor='nw')


        self.click_select_number = False

        self.s = Sudoku()


    def changeNumber(self,row, col):
        window_select_number = tk.Toplevel(self.main_window)
        window_select_number.geometry("250x250")
        window_select_number.title("Select Number You Want")
        lb = tk.Listbox(window_select_number, width=20,
                            height=50, listvariable=None)
        for item in range(1, 10):
            lb.insert("end", item)
        lb.place(x=0, y = 0, anchor='nw')

        var = tk.IntVar()
        def printSelectNumber():
            var.set(lb.get(lb.curselection()))
            self.s.sudoku[row][col] = var.get()
            if self.s.check():
                self.s.sudoku[row][col] = 0
                tk.messagebox.showwarning(title="Warning", message=str(
                    var.get()) + " has been existing!")
            else:
                self.createGrid()
                window_select_number.destroy()

        btn = tk.Button(window_select_number, text='确认', width=10,
                    height=2, command=printSelectNumber)
        btn.place(x=250, y = 150, anchor='se')
            

    def selectNumber(self,row, col):
            if self.click_select_number== False:
                self.click_select_number = True
                return
            self.click_select_number = False
            if self.s.origin_sudoku[row][col] != 0:
                tk.messagebox.showwarning(
                    title="Warning!", message="You cannot change the problem.")
            else:
                self.changeNumber(row, col)


    def createGrid(self):

        if self.s.checkSuccess():
            if tk.messagebox.askquestion(title="Success!", message="Congratulations!\n是否退出？") == "yes":
                main_window.quit()
            else:
                newGame()
            return

        for rowindex in range(9):
            for colindex in range(9):
                if (rowindex in (0, 1, 2, 6, 7, 8) and colindex in (3, 4, 5) or
                        (rowindex in (3, 4, 5) and colindex in (0, 1, 2, 6, 7, 8))):
                    colour = "light blue"
                else:
                    colour = "white"

                i = 0
                x = self.s.sudoku[rowindex+1][colindex+1]
                i = i+1
                if i == 81:
                    i = 0

                colourTxt = "black"
                if x == 0:
                    colourTxt = "red"
                else:
                    if self.s.covered[rowindex + 1][colindex + 1] == 0:
                        colourTxt = "green"
                    else:
                        colourTxt = "black"

                btn = Button(self.frame_sudoku, width=10, height=4, bg=colour, text=x, fg=colourTxt,font=28,
                            command=lambda row=rowindex, col=colindex: self.selectNumber(row+1, col+1))
                btn.grid(row=rowindex, column=colindex, sticky=N+S+E+W)
                # btn.grid(row=rowindex, column=colindex, sticky=N+S+E+W)


    def newGame(self):
        self.s.makeProblem()
        self.createGrid()

    def windowLoop(self):
        self.main_window.mainloop()


window = MainWindow()
window.windowLoop()
